package a_doubleWrite;

import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author: luolidong
 * @create: 2021-07-22 10:43
 * @version: 1.0
 */
public class L95 {
    public List<TreeNode> generateTrees(int n) {

        if (n == 0) return new ArrayList<>();

        return build(1, n);
    }

    private List<TreeNode> build(int left, int right) {
        List<TreeNode> list = new ArrayList<>();
        if (left > right) {
            list.add(null);
            return list;
        }
        for (int i = left; i <= right; i++) {
            //遍历构建树
            List<TreeNode> leftList = build(left, i - 1);
            List<TreeNode> rightList = build(i + 1, right);

            for (TreeNode l : leftList) {
                for (TreeNode r : rightList) {
                    TreeNode node = new TreeNode(i);
                    node.left = l;
                    node.right = r;
                    list.add(node);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        L95 l95 = new L95();
        List<TreeNode> list = l95.generateTrees(3);
        System.out.println(list);
    }
}
